HW#3 --- last modified February 28 2019 22:31:49..

Solution set.

Due date: Oct 17

Files to be submitted:
  Hw3.zip

Purpose: To gain familiarity with lex/yacc. To learn about variable scoping. To learn about one technique for mapping object-oriented languages into procedural ones.

Related Course Outcomes:

The main course outcomes covered by this assignment are:

(2)[Have a basic knowledge of the procedural, object-oriented, functional, and logic programming paradigms].

(5)[Read and produce context-free grammars].

(6)[Write recursive-descent parsers for simple languages, by hand or with a parser generator].

(7)[Understand variable scoping and lifetimes.]

Specification:

There are two parts to this assignment, a coding part and a writing part. Both should be submitted within the file Hw3.zip . The writing part should be contained in a plain text file called cplusplus.txt .

For the coding part of the assignment I want you to start with this YACC C 90 Grammar. Notice the page also has a link to a scanner for C as well. Make sure to read the faq for the grammar. It does have one shift/reduce conflict! The first thing I want you to do is to modify these so that on input a valid C program it just echoes the program to stdout. Next I want you to look at YACC C 99 Grammar. One of the differences between these two grammars is how the compound_statement non-terminal works. I want you to replace the compound_statement, statement_list rules in the older C with the rules for compound_statement, block_item_list, block_item in the newer grammar. Get echoing to work again with your new grammar. Now in gcc you can make the compiler compile as if it were a C90 compiler using the -ansi -pedantic options. You can also get gcc to just run the preprocessor (not the compiler) using the -E command. Take some C program and try just running the preprocessor on it. You will notice there will still be lines in the result that begin with `#'. For example, you might have a line like:

# 1 "/usr/include/stdio.h" 1 3 4

Modify your grammar and lexer so that such lines are all skipped and not echoed. Another thing that needs to be fixed to actual parse C is to remember the identifiers you have defined from previous typedef's. There is commented out code in the C lexer to help you get stated in doing this simple table check. You should also set it, so that if you see the string "__builtin_va_list" in the lexer you return TYPE_NAME. You will also need to get your lexer to echo but not send tokens for the __asm directives and for the __inline keyword. From this state your goal for the first part of the assignment is to make a second C pre-processor to be run after the gcc pre-processor which converts the C 99 compound statements into something can be compiled by the gcc with the -ansi -pedantic flags set. That is, the grader types "make all" after unzipping Hw3.zip. Then can move a file test.c into your directory. test.c might have compound statements which have declarations after statements in them. The grader then types:

gcc -E test.c -o i_test.c

./preprocessor < i_test.c > ii_test.c

gcc -ansi ii_test.c -o test

./test

And the code for the program test should run. You will probably get warnings that C90 does not support long long. That is okay. You should not get warning like: ISO C90 forbids mixed declarations and code. Here "preprocessor" is the name I want you to call the executable created by "make all". One way to write preprocessor is to leave the ECHO command as is in the C90 lexer. In the case where you are parsing a block_item_list if the leftmost block_item is a statement, let the rest of the block item list be denoted by "rest". In this case, you should output "statement { rest"; if it is just a declaration leave the block_item_list unchanged. block_item_list only occurs while parsing a compound_statement. At the close of the compound statement you will need to close all the extra braces you have opened, so you will need to get a count of these from the block_item_list in the rule:

compound_statement goes to '{' block_item_list '}'

That completes the description of the coding part of the assignment. For the written part of the assignment, I want you to imagine you were trying to create a pre-processor to convert C++ into C. As a cheap first step, we could imagine a class definition without member functions as being essentially structs, except the syntax:

class myclass
{
  //some declarations
};

struct special_prefix_myclass
{
  //the same declarations
};
typedef struct special_prefix_myclass;

As a next step, we could allow member function prototypes within the class definition. The preprocessor could map these to function pointer declarations in the output struct after preprocessing. So:

class myclass
{
  //some declarations
  void myfunc();
};

struct special_prefix_myclass
{
  //the same declarations
  void (*myfunc)(struct special_prefix_myclass this);
};
typedef struct special_prefix_myclass myclass;

The preprocessor would also maintain the names of these member functions in a symbol table. When a member function was given a definition:

void myclass::myfunc()
{
  //some code
}

the preprocessor could output:

void special_prefix_myclass__myfunc(struct special_prefix_myclass this)
{
  //the same code provided to refer to class field myfield used this.myfield 
}

Now suppose the input to the C++ preprocessor had declarations like:

myclass my_var;
int a;

In your file cplusplus.txt I would like you to describe what would need to be output by the C++ preprocessor to handle this declaration, so that it could be compiled by a C90 compiler (remember C++ was initially implemented as a preprocessor in the early 80s), and so that the functions pointers are correctly bound to their definitions. Besides this other code changes might need to be made, for instance, the preprocessor might need to switch a call like: my_var.myfunc(); to my_var.(*myfunc)(mv_var); , but you do not need to worry about them. However, you should pick one additional feature of C++, such as constructors; inheritance; public, private, protected keywords; and suggest how it could be implemented by such a C++ preprocessor.

Point Breakdown